1 Summary

This R Notebook generates figures in Sequencing-based Simulation Analysis section in manuscript.

  1. Inputs:

  2. Outputs:

    • Table. Median RMSE, JSD, correlation and FDR of all methods in Scenario 1
    • Figure. Boxplot of performance of all methods in Scenario 1
    • Figure. Pie chart of cell type proportions of all methods in Scenario 1

2 Version

version[['version.string']]
[1] "R version 4.2.2 Patched (2022-11-10 r83330)"
print(sprintf('Package %s version: %s', 'ggplot2', packageVersion('ggplot2')))
[1] "Package ggplot2 version: 3.4.2"
print(sprintf('Package %s version: %s', 'ggpubr', packageVersion('ggpubr')))
[1] "Package ggpubr version: 0.6.0"
print(sprintf('Package %s version: %s', 'philentropy', packageVersion('philentropy'))) # JSD function
[1] "Package philentropy version: 0.7.0"

3 Read locations of spatial spots

file_name = file.path(home.dir, 'sim_spatial_spot_loc.csv')
loc_df = read.csv(file_name, row.names = 1, check.names = F)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/Figures/Simulation_seq_based/sim_spatial_spot_loc.csv"

4 Read estimated cell type proportions by all methods

file_name = file.path(home.dir, 'simulation_seq_based_all_results.rds')
all_res = readRDS(file_name)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/Figures/Simulation_seq_based/simulation_seq_based_all_results.rds"

5 Quality control

5.1 Variable order

Check the order of spots and cell types are consistent before performance evaluation.

for (scenario in names(all_res)) {
  if (scenario != 'Truth') {
    for (method_name in names(all_res[[scenario]])) {
      stopifnot(all(row.names(all_res[[scenario]][[method_name]]) == row.names(all_res$Truth)))
      stopifnot(all(colnames(all_res[[scenario]][[method_name]]) == colnames(all_res$Truth)))
    }
  }
}

5.2 Negative proportions

Check whether negative values of estimated cell type proportions exist, as negative values may cause error in JSD calculation and got NaN. Replace them as 0.

for (scenario in names(all_res)) {
  if (scenario != 'Truth') {
    for (method_name in names(all_res[[scenario]])) {
      tmp_df = all_res[[scenario]][[method_name]]
      for (i in 1:nrow(tmp_df)) {
        for (j in 1:ncol(tmp_df)) {
          if (tmp_df[i, j] < 0) {
            print(sprintf('%s: %s result: row %d (%s) column %d (%s) has negative value %g', scenario, method_name, i, row.names(tmp_df)[i], j, colnames(tmp_df)[j], tmp_df[i, j]))
            # replace them with 0
            all_res[[scenario]][[method_name]][i, j] = 0
          }
        }
      }
    }
  }
}
[1] "S1_int_ref: SpatialDWLS result: row 125 (x7534y3550) column 4 (eL5) has negative value -1.84573e-19"
[1] "S1_int_ref: SpatialDWLS result: row 143 (x6034y4050) column 4 (eL5) has negative value -2.1962e-18"
[1] "S1_int_ref: SpatialDWLS result: row 291 (x9034y7550) column 2 (eL2/3) has negative value -4.23995e-19"
[1] "S1_int_ref: SpatialDWLS result: row 449 (x5534y11550) column 4 (eL5) has negative value -4.11672e-19"
[1] "S1_ext_ref: SpatialDWLS result: row 1 (x34y50) column 4 (eL5) has negative value -1.96899e-19"
[1] "S1_ext_ref: SpatialDWLS result: row 43 (x5534y1550) column 2 (eL2/3) has negative value -7.23067e-19"
[1] "S1_ext_ref: SpatialDWLS result: row 45 (x6534y1550) column 2 (eL2/3) has negative value -2.65685e-14"
[1] "S1_ext_ref: SpatialDWLS result: row 45 (x6534y1550) column 3 (eL4) has negative value -2.92345e-14"
[1] "S1_ext_ref: SpatialDWLS result: row 51 (x9534y1550) column 2 (eL2/3) has negative value -2.71336e-16"
[1] "S1_ext_ref: SpatialDWLS result: row 51 (x9534y1550) column 3 (eL4) has negative value -1.02778e-15"
[1] "S1_ext_ref: SpatialDWLS result: row 51 (x9534y1550) column 4 (eL5) has negative value -1.07852e-17"
[1] "S1_ext_ref: SpatialDWLS result: row 86 (x9034y2550) column 2 (eL2/3) has negative value -1.19306e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 107 (x9034y3050) column 9 (PVALB) has negative value -3.80156e-19"
[1] "S1_ext_ref: SpatialDWLS result: row 159 (x3034y4550) column 3 (eL4) has negative value -1.70033e-16"
[1] "S1_ext_ref: SpatialDWLS result: row 261 (x4534y7050) column 3 (eL4) has negative value -1.34987e-14"
[1] "S1_ext_ref: SpatialDWLS result: row 261 (x4534y7050) column 4 (eL5) has negative value -1.10174e-17"
[1] "S1_ext_ref: SpatialDWLS result: row 271 (x9534y7050) column 2 (eL2/3) has negative value -4.90217e-19"
[1] "S1_ext_ref: SpatialDWLS result: row 271 (x9534y7050) column 5 (eL6) has negative value -1.03155e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 282 (x4534y7550) column 4 (eL5) has negative value -1.05241e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 293 (x10034y7550) column 4 (eL5) has negative value -5.88417e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 296 (x534y8050) column 5 (eL6) has negative value -1.55533e-20"
[1] "S1_ext_ref: SpatialDWLS result: row 296 (x534y8050) column 11 (SST) has negative value -9.29682e-23"
[1] "S1_ext_ref: SpatialDWLS result: row 297 (x1034y8050) column 2 (eL2/3) has negative value -1.14198e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 297 (x1034y8050) column 11 (SST) has negative value -3.95337e-20"
[1] "S1_ext_ref: SpatialDWLS result: row 308 (x7534y8050) column 5 (eL6) has negative value -1.46301e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 359 (x2034y9550) column 5 (eL6) has negative value -1.05317e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 388 (x6534y10050) column 4 (eL5) has negative value -3.49281e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 425 (x3534y11050) column 2 (eL2/3) has negative value -5.31581e-21"
[1] "S1_ext_ref: SpatialDWLS result: row 440 (x534y11550) column 5 (eL6) has negative value -1.37485e-19"
[1] "S1_ext_ref: SpatialDWLS result: row 463 (x2034y12050) column 3 (eL4) has negative value -6.39067e-16"
[1] "S1_ext_ref: SpatialDWLS result: row 467 (x4534y12050) column 4 (eL5) has negative value -1.49888e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 492 (x7034y12550) column 9 (PVALB) has negative value -8.46644e-20"
[1] "S1_ext_ref: SpatialDWLS result: row 523 (x2534y13550) column 4 (eL5) has negative value -2.521e-18"
[1] "S1_ext_ref: SpatialDWLS result: row 538 (x1034y14050) column 5 (eL6) has negative value -3.46966e-19"
[1] "S1_ext_ref: SpatialDWLS result: row 558 (x3034y14550) column 5 (eL6) has negative value -1.14858e-17"
[1] "S1_ext_ref: SpatialDWLS result: row 565 (x3034y15050) column 4 (eL5) has negative value -5.83219e-19"

5.3 ALL 0s

Check whether estimated cell type proportions of spot are ALL 0s.

for (scenario in names(all_res)) {
  if (scenario != 'Truth') {
    for (method_name in names(all_res[[scenario]])) {
      tmp_df = all_res[[scenario]][[method_name]]
      for (i in 1:nrow(tmp_df)) {
        if (sum(tmp_df[i, ]) == 0) {
          print(sprintf('%s: %s result: row %d (%s) has ALL 0s', scenario, method_name, i, row.names(tmp_df)[i]))
        }
      }
    }
  }
}
[1] "S1_ext_ref: SpatialDWLS result: row 2 (x534y50) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 3 (x1034y50) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 4 (x1534y50) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 5 (x2034y50) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 10 (x2534y550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 11 (x4534y550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 21 (x1034y1050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 23 (x2034y1050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 28 (x5534y1050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 207 (x8034y5550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 223 (x6034y6050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 288 (x7534y7550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 316 (x534y8550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 318 (x1534y8550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 319 (x2034y8550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 341 (x3034y9050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 383 (x3534y10050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 513 (x7534y13050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 529 (x6034y13550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 550 (x9534y14050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 553 (x34y14550) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 561 (x534y15050) has ALL 0s"
[1] "S1_ext_ref: SpatialDWLS result: row 563 (x2034y15050) has ALL 0s"

5.4 Hard-thresholding (NOT applied)

For the methods without cell type selection procedure, including cell2location, DestVI, CARD and SONAR, we put a hard-thresholding with cutoff 0.1 on the estimated cell type compositions to force the extremely small proportions to be zeros.

UPDATE: hard-thresholding were NOT applied, original estimated cell type proportions were used for performance evaluation.

6 Evaluate performance of cell type deconvolution methods

6.1 Calculate spot-wise performance of all methods

4 performance measurements:

  • root mean square error (RMSE): quantifies the overall estimation accuracy
  • Jensen-Shannon Divergence (JSD): assesses similarity between the estimated cell type distribution and ground-truth per spot
  • Pearson’s correlation coefficient: measures the similarity of estimation to ground-truth
  • false discovery rate (FDR): measures how many cell types were falsely predicted to be present

NOTE:

  • in SpatialDWLS result, rows with ALL 0s may cause performance values to be NA or NaN.
binaryPredEvaluation = function(truth, pred) {
  # Given an array of truth and predictions (either 0 or 1), calculate confusion matrix
  # convert to factors to ensure get a full 2*2 confusion matrix
  truth_factor = factor(truth, levels = c(0, 1))
  pred_factor = factor(pred, levels = c(0, 1))
  # Generate confusion matrix
  conf_matrix = table(Actual = truth_factor, Predicted = pred_factor)
  # Extract elements of the confusion matrix
  TP = conf_matrix[2, 2]
  FP = conf_matrix[1, 2]
  FN = conf_matrix[2, 1]
  TN = conf_matrix[1, 1]
  # Calculate FDR (False Discovery Rate)
  FDR = FP / (TP + FP)
  # Calculate FNR (False Negative Rate)
  FNR = FN / (TP + FN)
  return(c(FDR, FNR))
}

calcPerformance = function(truth, pred) {
  # calculate RMSE, JSD, correlation and FDR for each row
  # inputs are matrix with rows as spots and columns as cell types, order has been checked to be consistent
  stopifnot(all(row.names(truth) == row.names(pred)))
  stopifnot(all(colnames(truth) == colnames(pred)))
  
  # binary cell type proportions (0:absent; 1:present)
  truth_binary = truth != 0
  pred_binary = pred != 0
  # in-place conversion from bool to 0/1 while keeping dimensions, row names and column names, as `as.numeric()` will "flattern" the original matrix
  truth_binary[] = as.numeric(truth_binary)
  pred_binary[] = as.numeric(pred_binary)
  
  perform_df = data.frame(RMSE=numeric(), JSD=numeric(), Pearson=numeric(), FDR=numeric(), FNR=numeric(), stringsAsFactors = F)
  
  for (i in 1:nrow(truth)) {
    RMSE = sqrt(mean((truth[i,] - pred[i,]) ^ 2))
    if (sum(pred[i,])>0 & sum(truth[i,])>0) {
      JSD = philentropy::JSD(rbind(truth[i,], pred[i,]), unit = 'log2', est.prob = 'empirical')
    } else {
      JSD = 1
    }
    Pearson = cor.test(truth[i,], pred[i,])$estimate
    tmp = binaryPredEvaluation(truth_binary[i,], pred_binary[i,])
    FDR = tmp[1]
    FNR = tmp[2]
    
    perform_df[nrow(perform_df)+1, ] = c(RMSE, JSD, Pearson, FDR, FNR)
  }
  
  # also record spot names
  stopifnot(nrow(perform_df) == nrow(truth))
  perform_df['Spot'] = row.names(truth)
  
  return(perform_df)
}


all_perform = list()

for (scenario in names(all_res)) {
  if (scenario != 'Truth') {
    all_perform[[scenario]] = list()
    for (method_name in names(all_res[[scenario]])) {
      all_perform[[scenario]][[method_name]] = calcPerformance(as.matrix(all_res[['Truth']]), as.matrix(all_res[[scenario]][[method_name]]))
    }
  }   
}

For rows with ALL 0s in SpatialDWLS performance, replace NA Pearson’s correlation coefficient as 0, NaN FDR as 0.

for (scenario in names(all_perform)) {
  tmp_df = all_perform[[scenario]][['SpatialDWLS']]
  tmp_df[is.na(tmp_df)] = 0
  all_perform[[scenario]][['SpatialDWLS']] = tmp_df
}

6.2 Summary spot-wise performance into method-wise

Including Table. Median RMSE, JSD, correlation, FDR and FNR of all methods in Scenario 1.

perform_raw_df = data.frame(Scenario=character(), Method=character(), Reference=character(), Spot=character(),
                            RMSE=numeric(), JSD=numeric(), Pearson=numeric(), FDR=numeric(), FNR=numeric(),
                            stringsAsFactors = F)

# calculate median performance across all spatial spots for all methods
perform_median_df = data.frame(Scenario=character(), Method=character(), Reference=character(),
                               median_RMSE=numeric(), median_JSD=numeric(), median_Pearson=numeric(), median_FDR=numeric(), median_FNR=numeric(),
                               stringsAsFactors = F)

for (scenario in names(all_perform)) {
  if (scenario == "S1_int_ref") {
    this_scenario = 'Scenario 1'
    this_ref = 'Internal'
  } else if (scenario == "S1_ext_ref") {
    this_scenario = 'Scenario 1'
    this_ref = 'External'
  } else if (scenario == 'S2_ext_ref') {
    this_scenario = 'Scenario 2'
    this_ref = 'External'
  } else {
    this_scenario = 'Scenario 3'
    this_ref = 'External'
  }
  
  for (method_name in names(all_perform[[scenario]])) {
    tmp_df = all_perform[[scenario]][[method_name]]
    tmp_df['Scenario'] = this_scenario
    tmp_df['Method'] = method_name
    tmp_df['Reference'] = this_ref
    
    perform_raw_df = rbind(perform_raw_df, tmp_df[, c('Scenario', 'Method', 'Reference', 'Spot', 'RMSE', 'JSD', 'Pearson', 'FDR', 'FNR')])
    
    # use list() instead of c() to keep data type, otherwise c() will coerce all elements to a common type like string
    perform_median_df[nrow(perform_median_df)+1, ] = list(this_scenario, method_name, this_ref,
                                                          round(median(tmp_df$RMSE), 3),
                                                          round(median(tmp_df$JSD), 3),
                                                          round(median(tmp_df$Pearson), 3),
                                                          round(median(tmp_df$FDR), 3),
                                                          round(median(tmp_df$FNR), 3))
  }
}

# set method column as factors
perform_raw_df['Method'] = factor(perform_raw_df$Method, levels = names(method_color))

perform_median_df[, c('Scenario', 'Method', 'Reference', 'median_RMSE', 'median_JSD', 'median_Pearson', 'median_FDR', 'median_FNR')]

7 Draw figures

7.1 Figure. Boxplot of performance of all methods in Scenario 1

if (save_file) {
  file_name = file.path(home.dir, 'Fig_sequencing_based_performance.pdf')
  cairo_pdf(file_name, height=6, width=6.5, onefile=T)
  print(sprintf('figures saved in file %s', file_name))
}

plot_df = perform_raw_df %>%
  filter(Scenario=='Scenario 1')

g_list = list()

for (perform_ind in c('RMSE', 'Pearson', 'JSD', 'FDR')) {
  g_list[[perform_ind]] = ggplot(plot_df, aes(x=Method, y=.data[[perform_ind]], fill=Method)) +
                            geom_boxplot(position=position_dodge(), outlier.shape=NA) +
                            scale_fill_manual(values=method_color) +
                            theme_classic() +
                            theme(strip.text = element_text(size=10),
                                  axis.text = element_text(color="black"),
                                  axis.ticks.x = element_blank(),
                                  axis.text.x = element_blank(),
                                  axis.title.x = element_blank(),
                                  legend.title = element_blank()) +
                            facet_grid(~Reference)
}

g_list[['Pearson']] = g_list[['Pearson']] + geom_hline(yintercept=0, color="red", linetype="dashed")

ggpubr::ggarrange(plotlist=g_list, ncol=2, nrow=2, common.legend=TRUE, legend="right")

7.2 Addtional boxplot for FNR

ggplot(plot_df, aes(x=Method, y=FNR, fill=Method)) +
  geom_boxplot(position=position_dodge(), outlier.shape=NA) +
  scale_fill_manual(values=method_color) +
  theme_classic() +
  theme(strip.text = element_text(size=10),
        axis.text = element_text(color="black"),
        axis.ticks.x = element_blank(),
        axis.text.x = element_blank(),
        axis.title.x = element_blank(),
        legend.title = element_blank()) +
  facet_grid(~Reference)

7.3 Figure. Pie chart of all methods in Scenario 1

7.3.1 Internal reference

if (save_file) {
  file_name = file.path(home.dir, 'Fig_sequencing_based_piechart_internal_ref.pdf')
  cairo_pdf(file_name, height=21, width=19.5, onefile=T)
  print(sprintf('figures saved in file %s', file_name))
}

g_list = list()


all_methods = names(method_color)
all_cts = colnames(all_res$Truth)

for (one_method in all_methods) {
  plot_df = merge(all_res$S1_int_ref[[one_method]], loc_df[, c('x', 'y')], by='row.names')
  g_list[[length(g_list)+1]] = ggplot() +
    geom_scatterpie(aes(x=x, y=y), data=plot_df, cols=all_cts) +
    scale_fill_manual(values=my_color) +
    theme_classic() +
    ggtitle(one_method) +
    theme(axis.title=element_blank(), axis.text=element_blank(), axis.ticks=element_blank(), axis.line=element_blank(),
      legend.title=element_blank(), legend.text=element_text(size=15),
      plot.title=element_text(size=17, face='bold', hjust=0.1))
}

ggpubr::ggarrange(plotlist = g_list, ncol = 3, nrow = 3, align = 'hv', common.legend = T, legend = 'right', font.label = list(size=17))

7.3.2 External reference

if (save_file) {
  file_name = file.path(home.dir, 'Fig_sequencing_based_piechart_external_ref.pdf')
  cairo_pdf(file_name, height=21, width=19.5, onefile=T)
  print(sprintf('figures saved in file %s', file_name))
}

g_list = list()


all_methods = names(method_color)
all_cts = colnames(all_res$Truth)

for (one_method in all_methods) {
  plot_df = merge(all_res$S1_ext_ref[[one_method]], loc_df[, c('x', 'y')], by='row.names')
  g_list[[length(g_list)+1]] = ggplot() +
    geom_scatterpie(aes(x=x, y=y), data=plot_df, cols=all_cts) +
    scale_fill_manual(values=my_color) +
    theme_classic() +
    ggtitle(one_method) +
    theme(axis.title=element_blank(), axis.text=element_blank(), axis.ticks=element_blank(), axis.line=element_blank(),
      legend.title=element_blank(), legend.text=element_text(size=15),
      plot.title=element_text(size=17, face='bold', hjust=0.1))
}

ggpubr::ggarrange(plotlist = g_list, ncol = 3, nrow = 3, align = 'hv', common.legend = T, legend = 'right', font.label = list(size=17))

LS0tCnRpdGxlOiAiR2VuZXJhdGUgZmlndXJlcyBpbiAqU2VxdWVuY2luZy1iYXNlZCogU2ltdWxhdGlvbiBBbmFseXNpcyIKYXV0aG9yOiAiTmluZ3NoYW4gTGkgJiBZdW5xaW5nIExpdSIKZGF0ZTogIjIwMjQvMDUvMDkiCm91dHB1dDogCiAgaHRtbF9ub3RlYm9vazoKICAgIGNvZGVfZm9sZGluZzogaGlkZQogICAgaGlnaGxpZ2h0OiB0YW5nbwogICAgbnVtYmVyX3NlY3Rpb25zOiB5ZXMKICAgIHRoZW1lOiB1bml0ZWQKICAgIHRvYzogeWVzCiAgICB0b2NfZGVwdGg6IDYKICAgIHRvY19mbG9hdDogeWVzCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSwgZXZhbCA9IFRSVUUsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFLCByZXN1bHRzPSdob2xkJywgZmlnLndpZHRoID0gNywgZmlnLmhlaWdodCA9IDUsIGRwaSA9IDMwMCkKCgojIHVzZSBnZ3B1YnIgcGFja2FnZSAoaHR0cDovL3d3dy5zdGhkYS5jb20vZW5nbGlzaC9hcnRpY2xlcy8yNC1nZ3B1YnItcHVibGljYXRpb24tcmVhZHktcGxvdHMvODEtZ2dwbG90Mi1lYXN5LXdheS10by1taXgtbXVsdGlwbGUtZ3JhcGhzLW9uLXRoZS1zYW1lLXBhZ2UvKQpsaWJyYXJ5KGRwbHlyKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoc2NhdHRlcnBpZSkKCgpgJW5vdGluJWAgPSBOZWdhdGUoYCVpbiVgKQoKc2V0LnNlZWQoMSkKCmhvbWUuZGlyID0gJy9ob21lL2hpbGwxMDMvRG9jdW1lbnRzL1NwYXRpYWwvRmlndXJlcy9TaW11bGF0aW9uX3NlcV9iYXNlZCcKc2F2ZV9maWxlID0gRkFMU0UKCm15X2NvbG9yID0gYygnI2U2MTk0YicsICcjM2NiNDRiJywgJyNmZmUxMTknLCAnIzQzNjNkOCcsICcjZjU4MjMxJywgJyM5MTFlYjQnLCAnIzQ2ZjBmMCcsICcjZjAzMmU2JywgJyNiY2Y2MGMnLCAnI2ZhYmViZScsICcjMDA4MDgwJywgJyNlNmJlZmYnLCAnIzlhNjMyNCcsICcjZmZmYWM4JywgJyM4MDAwMDAnLCAnI2FhZmZjMycsICcjODA4MDAwJywgJyNmZmQ4YjEnLCAnIzAwMDA3NScsICcjODA4MDgwJywgJyNmZmZmZmYnLCAnIzAwMDAwMCcpCm1ldGhvZF9jb2xvciA9IGMoIlNEZVBFUiI9JyNFNjE5NEInLCAiR0xSTSI9JyNGMDMyRTYnLCAiUkNURCI9JyM0NkYwRjAnLCAiU3BhdGlhbERXTFMiPScjM0NCNDRCJywgImNlbGwybG9jYXRpb24iPScjRkZFMTE5JywiU09OQVIiPScjOUE2MzI0JywgIlNQT1RsaWdodCI9JyM0MzYzRDgnLCAiQ0FSRCI9JyNGNTgyMzEnLCAiRGVzdFZJIj0nIzkxMUVCNCcpCmBgYAoKCiMgU3VtbWFyeQoKVGhpcyBSIE5vdGVib29rIGdlbmVyYXRlcyBmaWd1cmVzIGluICoqU2VxdWVuY2luZy1iYXNlZCBTaW11bGF0aW9uIEFuYWx5c2lzKiogc2VjdGlvbiBpbiBtYW51c2NyaXB0LgoKMS4gKipJbnB1dHMqKjoKCiAgICAqIFtgc2ltdWxhdGlvbl9zZXFfYmFzZWRfYWxsX3Jlc3VsdHMucmRzYF0oaHR0cHM6Ly9naXRodWIuY29tL2F6N2poMi9TRGVQRVJfQW5hbHlzaXMvYmxvYi9tYWluL0ZpZ3VyZXMvU2ltdWxhdGlvbl9zZXFfYmFzZWQvc2ltdWxhdGlvbl9zZXFfYmFzZWRfYWxsX3Jlc3VsdHMucmRzKTogY2VsbCB0eXBlIGRlY29udm9sdXRpb24gcmVzdWx0cyBvZiBhbGwgbWV0aG9kcywgYXMgd2VsbCBhcyB0aGUgZ3JvdW5kIHRydXRoIGluIHNlcXVlbmNpbmctYmFzZWQgc2ltdWxhdGlvbiBhbmFseXNpcy4KICAgICogW2BzaW1fc3BhdGlhbF9zcG90X2xvYy5jc3ZgXShodHRwczovL2dpdGh1Yi5jb20vYXo3amgyL1NEZVBFUl9BbmFseXNpcy9ibG9iL21haW4vU2ltdWxhdGlvbi9HZW5lcmF0ZV9zaW11bGF0aW9uX2RhdGEvc2ltX3NwYXRpYWxfc3BvdF9sb2MuY3N2KTogcGh5c2ljYWwgbG9jYXRpb25zIG9mIHNwYXRpYWwgc3BvdHMuCgoyLiAqKk91dHB1dHMqKjoKCiAgICAqIFRhYmxlLiBNZWRpYW4gUk1TRSwgSlNELCBjb3JyZWxhdGlvbiBhbmQgRkRSIG9mIGFsbCBtZXRob2RzIGluIFNjZW5hcmlvIDEKICAgICogRmlndXJlLiBCb3hwbG90IG9mIHBlcmZvcm1hbmNlIG9mIGFsbCBtZXRob2RzIGluIFNjZW5hcmlvIDEKICAgICogRmlndXJlLiBQaWUgY2hhcnQgb2YgY2VsbCB0eXBlIHByb3BvcnRpb25zIG9mIGFsbCBtZXRob2RzIGluIFNjZW5hcmlvIDEKCgojIFZlcnNpb24KCmBgYHtyfQp2ZXJzaW9uW1sndmVyc2lvbi5zdHJpbmcnXV0KcHJpbnQoc3ByaW50ZignUGFja2FnZSAlcyB2ZXJzaW9uOiAlcycsICdnZ3Bsb3QyJywgcGFja2FnZVZlcnNpb24oJ2dncGxvdDInKSkpCnByaW50KHNwcmludGYoJ1BhY2thZ2UgJXMgdmVyc2lvbjogJXMnLCAnZ2dwdWJyJywgcGFja2FnZVZlcnNpb24oJ2dncHVicicpKSkKcHJpbnQoc3ByaW50ZignUGFja2FnZSAlcyB2ZXJzaW9uOiAlcycsICdwaGlsZW50cm9weScsIHBhY2thZ2VWZXJzaW9uKCdwaGlsZW50cm9weScpKSkgIyBKU0QgZnVuY3Rpb24KYGBgCgojIFJlYWQgbG9jYXRpb25zIG9mIHNwYXRpYWwgc3BvdHMKCmBgYHtyfQpmaWxlX25hbWUgPSBmaWxlLnBhdGgoaG9tZS5kaXIsICdzaW1fc3BhdGlhbF9zcG90X2xvYy5jc3YnKQpsb2NfZGYgPSByZWFkLmNzdihmaWxlX25hbWUsIHJvdy5uYW1lcyA9IDEsIGNoZWNrLm5hbWVzID0gRikKcHJpbnQoc3ByaW50ZignbG9hZCBkYXRhIGZyb20gJXMnLCBmaWxlX25hbWUpKQpgYGAKCgojIFJlYWQgZXN0aW1hdGVkIGNlbGwgdHlwZSBwcm9wb3J0aW9ucyBieSBhbGwgbWV0aG9kcwoKYGBge3J9CmZpbGVfbmFtZSA9IGZpbGUucGF0aChob21lLmRpciwgJ3NpbXVsYXRpb25fc2VxX2Jhc2VkX2FsbF9yZXN1bHRzLnJkcycpCmFsbF9yZXMgPSByZWFkUkRTKGZpbGVfbmFtZSkKcHJpbnQoc3ByaW50ZignbG9hZCBkYXRhIGZyb20gJXMnLCBmaWxlX25hbWUpKQpgYGAKCgojIFF1YWxpdHkgY29udHJvbAoKIyMgVmFyaWFibGUgb3JkZXIKCkNoZWNrIHRoZSBvcmRlciBvZiBzcG90cyBhbmQgY2VsbCB0eXBlcyBhcmUgY29uc2lzdGVudCBiZWZvcmUgcGVyZm9ybWFuY2UgZXZhbHVhdGlvbi4KCmBgYHtyfQpmb3IgKHNjZW5hcmlvIGluIG5hbWVzKGFsbF9yZXMpKSB7CiAgaWYgKHNjZW5hcmlvICE9ICdUcnV0aCcpIHsKICAgIGZvciAobWV0aG9kX25hbWUgaW4gbmFtZXMoYWxsX3Jlc1tbc2NlbmFyaW9dXSkpIHsKICAgICAgc3RvcGlmbm90KGFsbChyb3cubmFtZXMoYWxsX3Jlc1tbc2NlbmFyaW9dXVtbbWV0aG9kX25hbWVdXSkgPT0gcm93Lm5hbWVzKGFsbF9yZXMkVHJ1dGgpKSkKICAgICAgc3RvcGlmbm90KGFsbChjb2xuYW1lcyhhbGxfcmVzW1tzY2VuYXJpb11dW1ttZXRob2RfbmFtZV1dKSA9PSBjb2xuYW1lcyhhbGxfcmVzJFRydXRoKSkpCiAgICB9CiAgfQp9CmBgYAoKCiMjIE5lZ2F0aXZlIHByb3BvcnRpb25zCgpDaGVjayB3aGV0aGVyIG5lZ2F0aXZlIHZhbHVlcyBvZiBlc3RpbWF0ZWQgY2VsbCB0eXBlIHByb3BvcnRpb25zIGV4aXN0LCBhcyBuZWdhdGl2ZSB2YWx1ZXMgbWF5IGNhdXNlIGVycm9yIGluIEpTRCBjYWxjdWxhdGlvbiBhbmQgZ290IGBOYU5gLiBSZXBsYWNlIHRoZW0gYXMgMC4KCmBgYHtyfQpmb3IgKHNjZW5hcmlvIGluIG5hbWVzKGFsbF9yZXMpKSB7CiAgaWYgKHNjZW5hcmlvICE9ICdUcnV0aCcpIHsKICAgIGZvciAobWV0aG9kX25hbWUgaW4gbmFtZXMoYWxsX3Jlc1tbc2NlbmFyaW9dXSkpIHsKICAgICAgdG1wX2RmID0gYWxsX3Jlc1tbc2NlbmFyaW9dXVtbbWV0aG9kX25hbWVdXQogICAgICBmb3IgKGkgaW4gMTpucm93KHRtcF9kZikpIHsKICAgICAgICBmb3IgKGogaW4gMTpuY29sKHRtcF9kZikpIHsKICAgICAgICAgIGlmICh0bXBfZGZbaSwgal0gPCAwKSB7CiAgICAgICAgICAgIHByaW50KHNwcmludGYoJyVzOiAlcyByZXN1bHQ6IHJvdyAlZCAoJXMpIGNvbHVtbiAlZCAoJXMpIGhhcyBuZWdhdGl2ZSB2YWx1ZSAlZycsIHNjZW5hcmlvLCBtZXRob2RfbmFtZSwgaSwgcm93Lm5hbWVzKHRtcF9kZilbaV0sIGosIGNvbG5hbWVzKHRtcF9kZilbal0sIHRtcF9kZltpLCBqXSkpCiAgICAgICAgICAgICMgcmVwbGFjZSB0aGVtIHdpdGggMAogICAgICAgICAgICBhbGxfcmVzW1tzY2VuYXJpb11dW1ttZXRob2RfbmFtZV1dW2ksIGpdID0gMAogICAgICAgICAgfQogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KfQpgYGAKCiMjIEFMTCAwcwoKQ2hlY2sgd2hldGhlciBlc3RpbWF0ZWQgY2VsbCB0eXBlIHByb3BvcnRpb25zIG9mIHNwb3QgYXJlIEFMTCAwcy4KCmBgYHtyfQpmb3IgKHNjZW5hcmlvIGluIG5hbWVzKGFsbF9yZXMpKSB7CiAgaWYgKHNjZW5hcmlvICE9ICdUcnV0aCcpIHsKICAgIGZvciAobWV0aG9kX25hbWUgaW4gbmFtZXMoYWxsX3Jlc1tbc2NlbmFyaW9dXSkpIHsKICAgICAgdG1wX2RmID0gYWxsX3Jlc1tbc2NlbmFyaW9dXVtbbWV0aG9kX25hbWVdXQogICAgICBmb3IgKGkgaW4gMTpucm93KHRtcF9kZikpIHsKICAgICAgICBpZiAoc3VtKHRtcF9kZltpLCBdKSA9PSAwKSB7CiAgICAgICAgICBwcmludChzcHJpbnRmKCclczogJXMgcmVzdWx0OiByb3cgJWQgKCVzKSBoYXMgQUxMIDBzJywgc2NlbmFyaW8sIG1ldGhvZF9uYW1lLCBpLCByb3cubmFtZXModG1wX2RmKVtpXSkpCiAgICAgICAgfQogICAgICB9CiAgICB9CiAgfQp9CmBgYAoKIyMgSGFyZC10aHJlc2hvbGRpbmcgKE5PVCBhcHBsaWVkKQoKRm9yIHRoZSBtZXRob2RzIHdpdGhvdXQgY2VsbCB0eXBlIHNlbGVjdGlvbiBwcm9jZWR1cmUsIGluY2x1ZGluZyAqKmNlbGwybG9jYXRpb24qKiwgKipEZXN0VkkqKiwgKipDQVJEKiogYW5kICoqU09OQVIqKiwgd2UgcHV0IGEgaGFyZC10aHJlc2hvbGRpbmcgd2l0aCBjdXRvZmYgKiowLjEqKiBvbiB0aGUgZXN0aW1hdGVkIGNlbGwgdHlwZSBjb21wb3NpdGlvbnMgdG8gZm9yY2UgdGhlIGV4dHJlbWVseSBzbWFsbCBwcm9wb3J0aW9ucyB0byBiZSB6ZXJvcy4KCioqVVBEQVRFKio6IGhhcmQtdGhyZXNob2xkaW5nIHdlcmUgTk9UIGFwcGxpZWQsIG9yaWdpbmFsIGVzdGltYXRlZCBjZWxsIHR5cGUgcHJvcG9ydGlvbnMgd2VyZSB1c2VkIGZvciBwZXJmb3JtYW5jZSBldmFsdWF0aW9uLgoKCgojIEV2YWx1YXRlIHBlcmZvcm1hbmNlIG9mIGNlbGwgdHlwZSBkZWNvbnZvbHV0aW9uIG1ldGhvZHMKCiMjIENhbGN1bGF0ZSBzcG90LXdpc2UgcGVyZm9ybWFuY2Ugb2YgYWxsIG1ldGhvZHMKCjQgcGVyZm9ybWFuY2UgbWVhc3VyZW1lbnRzOgoKKiByb290IG1lYW4gc3F1YXJlIGVycm9yICgqKlJNU0UqKik6IHF1YW50aWZpZXMgdGhlIG92ZXJhbGwgZXN0aW1hdGlvbiBhY2N1cmFjeQoqIEplbnNlbi1TaGFubm9uIERpdmVyZ2VuY2UgKCoqSlNEKiopOiBhc3Nlc3NlcyBzaW1pbGFyaXR5IGJldHdlZW4gdGhlIGVzdGltYXRlZCBjZWxsIHR5cGUgZGlzdHJpYnV0aW9uIGFuZCBncm91bmQtdHJ1dGggcGVyIHNwb3QKKiAqKlBlYXJzb27igJlzIGNvcnJlbGF0aW9uIGNvZWZmaWNpZW50Kio6IG1lYXN1cmVzIHRoZSBzaW1pbGFyaXR5IG9mIGVzdGltYXRpb24gdG8gZ3JvdW5kLXRydXRoCiogZmFsc2UgZGlzY292ZXJ5IHJhdGUgKCoqRkRSKiopOiBtZWFzdXJlcyBob3cgbWFueSBjZWxsIHR5cGVzIHdlcmUgZmFsc2VseSBwcmVkaWN0ZWQgdG8gYmUgcHJlc2VudAoKTk9URToKCiogaW4gKipTcGF0aWFsRFdMUyoqIHJlc3VsdCwgcm93cyB3aXRoIEFMTCAwcyBtYXkgY2F1c2UgcGVyZm9ybWFuY2UgdmFsdWVzIHRvIGJlIGBOQWAgb3IgYE5hTmAuCgpgYGB7cn0KYmluYXJ5UHJlZEV2YWx1YXRpb24gPSBmdW5jdGlvbih0cnV0aCwgcHJlZCkgewogICMgR2l2ZW4gYW4gYXJyYXkgb2YgdHJ1dGggYW5kIHByZWRpY3Rpb25zIChlaXRoZXIgMCBvciAxKSwgY2FsY3VsYXRlIGNvbmZ1c2lvbiBtYXRyaXgKICAjIGNvbnZlcnQgdG8gZmFjdG9ycyB0byBlbnN1cmUgZ2V0IGEgZnVsbCAyKjIgY29uZnVzaW9uIG1hdHJpeAogIHRydXRoX2ZhY3RvciA9IGZhY3Rvcih0cnV0aCwgbGV2ZWxzID0gYygwLCAxKSkKICBwcmVkX2ZhY3RvciA9IGZhY3RvcihwcmVkLCBsZXZlbHMgPSBjKDAsIDEpKQogICMgR2VuZXJhdGUgY29uZnVzaW9uIG1hdHJpeAogIGNvbmZfbWF0cml4ID0gdGFibGUoQWN0dWFsID0gdHJ1dGhfZmFjdG9yLCBQcmVkaWN0ZWQgPSBwcmVkX2ZhY3RvcikKICAjIEV4dHJhY3QgZWxlbWVudHMgb2YgdGhlIGNvbmZ1c2lvbiBtYXRyaXgKICBUUCA9IGNvbmZfbWF0cml4WzIsIDJdCiAgRlAgPSBjb25mX21hdHJpeFsxLCAyXQogIEZOID0gY29uZl9tYXRyaXhbMiwgMV0KICBUTiA9IGNvbmZfbWF0cml4WzEsIDFdCiAgIyBDYWxjdWxhdGUgRkRSIChGYWxzZSBEaXNjb3ZlcnkgUmF0ZSkKICBGRFIgPSBGUCAvIChUUCArIEZQKQogICMgQ2FsY3VsYXRlIEZOUiAoRmFsc2UgTmVnYXRpdmUgUmF0ZSkKICBGTlIgPSBGTiAvIChUUCArIEZOKQogIHJldHVybihjKEZEUiwgRk5SKSkKfQoKY2FsY1BlcmZvcm1hbmNlID0gZnVuY3Rpb24odHJ1dGgsIHByZWQpIHsKICAjIGNhbGN1bGF0ZSBSTVNFLCBKU0QsIGNvcnJlbGF0aW9uIGFuZCBGRFIgZm9yIGVhY2ggcm93CiAgIyBpbnB1dHMgYXJlIG1hdHJpeCB3aXRoIHJvd3MgYXMgc3BvdHMgYW5kIGNvbHVtbnMgYXMgY2VsbCB0eXBlcywgb3JkZXIgaGFzIGJlZW4gY2hlY2tlZCB0byBiZSBjb25zaXN0ZW50CiAgc3RvcGlmbm90KGFsbChyb3cubmFtZXModHJ1dGgpID09IHJvdy5uYW1lcyhwcmVkKSkpCiAgc3RvcGlmbm90KGFsbChjb2xuYW1lcyh0cnV0aCkgPT0gY29sbmFtZXMocHJlZCkpKQogIAogICMgYmluYXJ5IGNlbGwgdHlwZSBwcm9wb3J0aW9ucyAoMDphYnNlbnQ7IDE6cHJlc2VudCkKICB0cnV0aF9iaW5hcnkgPSB0cnV0aCAhPSAwCiAgcHJlZF9iaW5hcnkgPSBwcmVkICE9IDAKICAjIGluLXBsYWNlIGNvbnZlcnNpb24gZnJvbSBib29sIHRvIDAvMSB3aGlsZSBrZWVwaW5nIGRpbWVuc2lvbnMsIHJvdyBuYW1lcyBhbmQgY29sdW1uIG5hbWVzLCBhcyBgYXMubnVtZXJpYygpYCB3aWxsICJmbGF0dGVybiIgdGhlIG9yaWdpbmFsIG1hdHJpeAogIHRydXRoX2JpbmFyeVtdID0gYXMubnVtZXJpYyh0cnV0aF9iaW5hcnkpCiAgcHJlZF9iaW5hcnlbXSA9IGFzLm51bWVyaWMocHJlZF9iaW5hcnkpCiAgCiAgcGVyZm9ybV9kZiA9IGRhdGEuZnJhbWUoUk1TRT1udW1lcmljKCksIEpTRD1udW1lcmljKCksIFBlYXJzb249bnVtZXJpYygpLCBGRFI9bnVtZXJpYygpLCBGTlI9bnVtZXJpYygpLCBzdHJpbmdzQXNGYWN0b3JzID0gRikKICAKICBmb3IgKGkgaW4gMTpucm93KHRydXRoKSkgewogICAgUk1TRSA9IHNxcnQobWVhbigodHJ1dGhbaSxdIC0gcHJlZFtpLF0pIF4gMikpCiAgICBpZiAoc3VtKHByZWRbaSxdKT4wICYgc3VtKHRydXRoW2ksXSk+MCkgewogICAgICBKU0QgPSBwaGlsZW50cm9weTo6SlNEKHJiaW5kKHRydXRoW2ksXSwgcHJlZFtpLF0pLCB1bml0ID0gJ2xvZzInLCBlc3QucHJvYiA9ICdlbXBpcmljYWwnKQogICAgfSBlbHNlIHsKICAgICAgSlNEID0gMQogICAgfQogICAgUGVhcnNvbiA9IGNvci50ZXN0KHRydXRoW2ksXSwgcHJlZFtpLF0pJGVzdGltYXRlCiAgICB0bXAgPSBiaW5hcnlQcmVkRXZhbHVhdGlvbih0cnV0aF9iaW5hcnlbaSxdLCBwcmVkX2JpbmFyeVtpLF0pCiAgICBGRFIgPSB0bXBbMV0KICAgIEZOUiA9IHRtcFsyXQogICAgCiAgICBwZXJmb3JtX2RmW25yb3cocGVyZm9ybV9kZikrMSwgXSA9IGMoUk1TRSwgSlNELCBQZWFyc29uLCBGRFIsIEZOUikKICB9CiAgCiAgIyBhbHNvIHJlY29yZCBzcG90IG5hbWVzCiAgc3RvcGlmbm90KG5yb3cocGVyZm9ybV9kZikgPT0gbnJvdyh0cnV0aCkpCiAgcGVyZm9ybV9kZlsnU3BvdCddID0gcm93Lm5hbWVzKHRydXRoKQogIAogIHJldHVybihwZXJmb3JtX2RmKQp9CgoKYWxsX3BlcmZvcm0gPSBsaXN0KCkKCmZvciAoc2NlbmFyaW8gaW4gbmFtZXMoYWxsX3JlcykpIHsKICBpZiAoc2NlbmFyaW8gIT0gJ1RydXRoJykgewogICAgYWxsX3BlcmZvcm1bW3NjZW5hcmlvXV0gPSBsaXN0KCkKICAgIGZvciAobWV0aG9kX25hbWUgaW4gbmFtZXMoYWxsX3Jlc1tbc2NlbmFyaW9dXSkpIHsKICAgICAgYWxsX3BlcmZvcm1bW3NjZW5hcmlvXV1bW21ldGhvZF9uYW1lXV0gPSBjYWxjUGVyZm9ybWFuY2UoYXMubWF0cml4KGFsbF9yZXNbWydUcnV0aCddXSksIGFzLm1hdHJpeChhbGxfcmVzW1tzY2VuYXJpb11dW1ttZXRob2RfbmFtZV1dKSkKICAgIH0KICB9ICAgCn0KYGBgCgoKRm9yIHJvd3Mgd2l0aCBBTEwgMHMgaW4gKipTcGF0aWFsRFdMUyoqIHBlcmZvcm1hbmNlLCByZXBsYWNlIGBOQWAgUGVhcnNvbuKAmXMgY29ycmVsYXRpb24gY29lZmZpY2llbnQgYXMgMCwgYE5hTmAgRkRSIGFzIDAuCgpgYGB7cn0KZm9yIChzY2VuYXJpbyBpbiBuYW1lcyhhbGxfcGVyZm9ybSkpIHsKICB0bXBfZGYgPSBhbGxfcGVyZm9ybVtbc2NlbmFyaW9dXVtbJ1NwYXRpYWxEV0xTJ11dCiAgdG1wX2RmW2lzLm5hKHRtcF9kZildID0gMAogIGFsbF9wZXJmb3JtW1tzY2VuYXJpb11dW1snU3BhdGlhbERXTFMnXV0gPSB0bXBfZGYKfQpgYGAKCgoKIyMgU3VtbWFyeSBzcG90LXdpc2UgcGVyZm9ybWFuY2UgaW50byBtZXRob2Qtd2lzZQoKSW5jbHVkaW5nIFRhYmxlLiBNZWRpYW4gUk1TRSwgSlNELCBjb3JyZWxhdGlvbiwgRkRSIGFuZCBGTlIgb2YgYWxsIG1ldGhvZHMgaW4gU2NlbmFyaW8gMS4KCmBgYHtyfQpwZXJmb3JtX3Jhd19kZiA9IGRhdGEuZnJhbWUoU2NlbmFyaW89Y2hhcmFjdGVyKCksIE1ldGhvZD1jaGFyYWN0ZXIoKSwgUmVmZXJlbmNlPWNoYXJhY3RlcigpLCBTcG90PWNoYXJhY3RlcigpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgUk1TRT1udW1lcmljKCksIEpTRD1udW1lcmljKCksIFBlYXJzb249bnVtZXJpYygpLCBGRFI9bnVtZXJpYygpLCBGTlI9bnVtZXJpYygpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RyaW5nc0FzRmFjdG9ycyA9IEYpCgojIGNhbGN1bGF0ZSBtZWRpYW4gcGVyZm9ybWFuY2UgYWNyb3NzIGFsbCBzcGF0aWFsIHNwb3RzIGZvciBhbGwgbWV0aG9kcwpwZXJmb3JtX21lZGlhbl9kZiA9IGRhdGEuZnJhbWUoU2NlbmFyaW89Y2hhcmFjdGVyKCksIE1ldGhvZD1jaGFyYWN0ZXIoKSwgUmVmZXJlbmNlPWNoYXJhY3RlcigpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWVkaWFuX1JNU0U9bnVtZXJpYygpLCBtZWRpYW5fSlNEPW51bWVyaWMoKSwgbWVkaWFuX1BlYXJzb249bnVtZXJpYygpLCBtZWRpYW5fRkRSPW51bWVyaWMoKSwgbWVkaWFuX0ZOUj1udW1lcmljKCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdHJpbmdzQXNGYWN0b3JzID0gRikKCmZvciAoc2NlbmFyaW8gaW4gbmFtZXMoYWxsX3BlcmZvcm0pKSB7CiAgaWYgKHNjZW5hcmlvID09ICJTMV9pbnRfcmVmIikgewogICAgdGhpc19zY2VuYXJpbyA9ICdTY2VuYXJpbyAxJwogICAgdGhpc19yZWYgPSAnSW50ZXJuYWwnCiAgfSBlbHNlIGlmIChzY2VuYXJpbyA9PSAiUzFfZXh0X3JlZiIpIHsKICAgIHRoaXNfc2NlbmFyaW8gPSAnU2NlbmFyaW8gMScKICAgIHRoaXNfcmVmID0gJ0V4dGVybmFsJwogIH0gZWxzZSBpZiAoc2NlbmFyaW8gPT0gJ1MyX2V4dF9yZWYnKSB7CiAgICB0aGlzX3NjZW5hcmlvID0gJ1NjZW5hcmlvIDInCiAgICB0aGlzX3JlZiA9ICdFeHRlcm5hbCcKICB9IGVsc2UgewogICAgdGhpc19zY2VuYXJpbyA9ICdTY2VuYXJpbyAzJwogICAgdGhpc19yZWYgPSAnRXh0ZXJuYWwnCiAgfQogIAogIGZvciAobWV0aG9kX25hbWUgaW4gbmFtZXMoYWxsX3BlcmZvcm1bW3NjZW5hcmlvXV0pKSB7CiAgICB0bXBfZGYgPSBhbGxfcGVyZm9ybVtbc2NlbmFyaW9dXVtbbWV0aG9kX25hbWVdXQogICAgdG1wX2RmWydTY2VuYXJpbyddID0gdGhpc19zY2VuYXJpbwogICAgdG1wX2RmWydNZXRob2QnXSA9IG1ldGhvZF9uYW1lCiAgICB0bXBfZGZbJ1JlZmVyZW5jZSddID0gdGhpc19yZWYKICAgIAogICAgcGVyZm9ybV9yYXdfZGYgPSByYmluZChwZXJmb3JtX3Jhd19kZiwgdG1wX2RmWywgYygnU2NlbmFyaW8nLCAnTWV0aG9kJywgJ1JlZmVyZW5jZScsICdTcG90JywgJ1JNU0UnLCAnSlNEJywgJ1BlYXJzb24nLCAnRkRSJywgJ0ZOUicpXSkKICAgIAogICAgIyB1c2UgbGlzdCgpIGluc3RlYWQgb2YgYygpIHRvIGtlZXAgZGF0YSB0eXBlLCBvdGhlcndpc2UgYygpIHdpbGwgY29lcmNlIGFsbCBlbGVtZW50cyB0byBhIGNvbW1vbiB0eXBlIGxpa2Ugc3RyaW5nCiAgICBwZXJmb3JtX21lZGlhbl9kZltucm93KHBlcmZvcm1fbWVkaWFuX2RmKSsxLCBdID0gbGlzdCh0aGlzX3NjZW5hcmlvLCBtZXRob2RfbmFtZSwgdGhpc19yZWYsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByb3VuZChtZWRpYW4odG1wX2RmJFJNU0UpLCAzKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJvdW5kKG1lZGlhbih0bXBfZGYkSlNEKSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByb3VuZChtZWRpYW4odG1wX2RmJFBlYXJzb24pLCAzKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJvdW5kKG1lZGlhbih0bXBfZGYkRkRSKSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByb3VuZChtZWRpYW4odG1wX2RmJEZOUiksIDMpKQogIH0KfQoKIyBzZXQgbWV0aG9kIGNvbHVtbiBhcyBmYWN0b3JzCnBlcmZvcm1fcmF3X2RmWydNZXRob2QnXSA9IGZhY3RvcihwZXJmb3JtX3Jhd19kZiRNZXRob2QsIGxldmVscyA9IG5hbWVzKG1ldGhvZF9jb2xvcikpCgpwZXJmb3JtX21lZGlhbl9kZlssIGMoJ1NjZW5hcmlvJywgJ01ldGhvZCcsICdSZWZlcmVuY2UnLCAnbWVkaWFuX1JNU0UnLCAnbWVkaWFuX0pTRCcsICdtZWRpYW5fUGVhcnNvbicsICdtZWRpYW5fRkRSJywgJ21lZGlhbl9GTlInKV0KYGBgCgoKCiMgRHJhdyBmaWd1cmVzCgojIyBGaWd1cmUuIEJveHBsb3Qgb2YgcGVyZm9ybWFuY2Ugb2YgYWxsIG1ldGhvZHMgaW4gU2NlbmFyaW8gMQoKYGBge3IsIGZpZy53aWR0aD02LjUsIGZpZy5oZWlnaHQ9Nn0KaWYgKHNhdmVfZmlsZSkgewogIGZpbGVfbmFtZSA9IGZpbGUucGF0aChob21lLmRpciwgJ0ZpZ19zZXF1ZW5jaW5nX2Jhc2VkX3BlcmZvcm1hbmNlLnBkZicpCiAgY2Fpcm9fcGRmKGZpbGVfbmFtZSwgaGVpZ2h0PTYsIHdpZHRoPTYuNSwgb25lZmlsZT1UKQogIHByaW50KHNwcmludGYoJ2ZpZ3VyZXMgc2F2ZWQgaW4gZmlsZSAlcycsIGZpbGVfbmFtZSkpCn0KCnBsb3RfZGYgPSBwZXJmb3JtX3Jhd19kZiAlPiUKICBmaWx0ZXIoU2NlbmFyaW89PSdTY2VuYXJpbyAxJykKCmdfbGlzdCA9IGxpc3QoKQoKZm9yIChwZXJmb3JtX2luZCBpbiBjKCdSTVNFJywgJ1BlYXJzb24nLCAnSlNEJywgJ0ZEUicpKSB7CiAgZ19saXN0W1twZXJmb3JtX2luZF1dID0gZ2dwbG90KHBsb3RfZGYsIGFlcyh4PU1ldGhvZCwgeT0uZGF0YVtbcGVyZm9ybV9pbmRdXSwgZmlsbD1NZXRob2QpKSArCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBnZW9tX2JveHBsb3QocG9zaXRpb249cG9zaXRpb25fZG9kZ2UoKSwgb3V0bGllci5zaGFwZT1OQSkgKwogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzPW1ldGhvZF9jb2xvcikgKwogICAgICAgICAgICAgICAgICAgICAgICAgICAgdGhlbWVfY2xhc3NpYygpICsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRoZW1lKHN0cmlwLnRleHQgPSBlbGVtZW50X3RleHQoc2l6ZT0xMCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBheGlzLnRleHQgPSBlbGVtZW50X3RleHQoY29sb3I9ImJsYWNrIiksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBheGlzLnRpY2tzLnggPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGF4aXMudGl0bGUueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxlZ2VuZC50aXRsZSA9IGVsZW1lbnRfYmxhbmsoKSkgKwogICAgICAgICAgICAgICAgICAgICAgICAgICAgZmFjZXRfZ3JpZCh+UmVmZXJlbmNlKQp9CgpnX2xpc3RbWydQZWFyc29uJ11dID0gZ19saXN0W1snUGVhcnNvbiddXSArIGdlb21faGxpbmUoeWludGVyY2VwdD0wLCBjb2xvcj0icmVkIiwgbGluZXR5cGU9ImRhc2hlZCIpCgpnZ3B1YnI6OmdnYXJyYW5nZShwbG90bGlzdD1nX2xpc3QsIG5jb2w9MiwgbnJvdz0yLCBjb21tb24ubGVnZW5kPVRSVUUsIGxlZ2VuZD0icmlnaHQiKQpgYGAKCgojIyBBZGR0aW9uYWwgYm94cGxvdCBmb3IgRk5SCgpgYGB7ciwgZmlnLndpZHRoPTQsIGZpZy5oZWlnaHQ9M30KZ2dwbG90KHBsb3RfZGYsIGFlcyh4PU1ldGhvZCwgeT1GTlIsIGZpbGw9TWV0aG9kKSkgKwogIGdlb21fYm94cGxvdChwb3NpdGlvbj1wb3NpdGlvbl9kb2RnZSgpLCBvdXRsaWVyLnNoYXBlPU5BKSArCiAgc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzPW1ldGhvZF9jb2xvcikgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgdGhlbWUoc3RyaXAudGV4dCA9IGVsZW1lbnRfdGV4dChzaXplPTEwKSwKICAgICAgICBheGlzLnRleHQgPSBlbGVtZW50X3RleHQoY29sb3I9ImJsYWNrIiksCiAgICAgICAgYXhpcy50aWNrcy54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGV4dC54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGl0bGUueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBsZWdlbmQudGl0bGUgPSBlbGVtZW50X2JsYW5rKCkpICsKICBmYWNldF9ncmlkKH5SZWZlcmVuY2UpCmBgYAoKCiMjIEZpZ3VyZS4gUGllIGNoYXJ0IG9mIGFsbCBtZXRob2RzIGluIFNjZW5hcmlvIDEKCiMjIyBJbnRlcm5hbCByZWZlcmVuY2UKCmBgYHtyLCBmaWcud2lkdGg9MTkuNSwgZmlnLmhlaWdodD0yMX0KaWYgKHNhdmVfZmlsZSkgewogIGZpbGVfbmFtZSA9IGZpbGUucGF0aChob21lLmRpciwgJ0ZpZ19zZXF1ZW5jaW5nX2Jhc2VkX3BpZWNoYXJ0X2ludGVybmFsX3JlZi5wZGYnKQogIGNhaXJvX3BkZihmaWxlX25hbWUsIGhlaWdodD0yMSwgd2lkdGg9MTkuNSwgb25lZmlsZT1UKQogIHByaW50KHNwcmludGYoJ2ZpZ3VyZXMgc2F2ZWQgaW4gZmlsZSAlcycsIGZpbGVfbmFtZSkpCn0KCmdfbGlzdCA9IGxpc3QoKQoKCmFsbF9tZXRob2RzID0gbmFtZXMobWV0aG9kX2NvbG9yKQphbGxfY3RzID0gY29sbmFtZXMoYWxsX3JlcyRUcnV0aCkKCmZvciAob25lX21ldGhvZCBpbiBhbGxfbWV0aG9kcykgewogIHBsb3RfZGYgPSBtZXJnZShhbGxfcmVzJFMxX2ludF9yZWZbW29uZV9tZXRob2RdXSwgbG9jX2RmWywgYygneCcsICd5JyldLCBieT0ncm93Lm5hbWVzJykKICBnX2xpc3RbW2xlbmd0aChnX2xpc3QpKzFdXSA9IGdncGxvdCgpICsKICAgIGdlb21fc2NhdHRlcnBpZShhZXMoeD14LCB5PXkpLCBkYXRhPXBsb3RfZGYsIGNvbHM9YWxsX2N0cykgKwogICAgc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzPW15X2NvbG9yKSArCiAgICB0aGVtZV9jbGFzc2ljKCkgKwogICAgZ2d0aXRsZShvbmVfbWV0aG9kKSArCiAgICB0aGVtZShheGlzLnRpdGxlPWVsZW1lbnRfYmxhbmsoKSwgYXhpcy50ZXh0PWVsZW1lbnRfYmxhbmsoKSwgYXhpcy50aWNrcz1lbGVtZW50X2JsYW5rKCksIGF4aXMubGluZT1lbGVtZW50X2JsYW5rKCksCiAgICAgIGxlZ2VuZC50aXRsZT1lbGVtZW50X2JsYW5rKCksIGxlZ2VuZC50ZXh0PWVsZW1lbnRfdGV4dChzaXplPTE1KSwKICAgICAgcGxvdC50aXRsZT1lbGVtZW50X3RleHQoc2l6ZT0xNywgZmFjZT0nYm9sZCcsIGhqdXN0PTAuMSkpCn0KCmdncHVicjo6Z2dhcnJhbmdlKHBsb3RsaXN0ID0gZ19saXN0LCBuY29sID0gMywgbnJvdyA9IDMsIGFsaWduID0gJ2h2JywgY29tbW9uLmxlZ2VuZCA9IFQsIGxlZ2VuZCA9ICdyaWdodCcsIGZvbnQubGFiZWwgPSBsaXN0KHNpemU9MTcpKQpgYGAKCgojIyMgRXh0ZXJuYWwgcmVmZXJlbmNlCgpgYGB7ciwgZmlnLndpZHRoPTE5LjUsIGZpZy5oZWlnaHQ9MjF9CmlmIChzYXZlX2ZpbGUpIHsKICBmaWxlX25hbWUgPSBmaWxlLnBhdGgoaG9tZS5kaXIsICdGaWdfc2VxdWVuY2luZ19iYXNlZF9waWVjaGFydF9leHRlcm5hbF9yZWYucGRmJykKICBjYWlyb19wZGYoZmlsZV9uYW1lLCBoZWlnaHQ9MjEsIHdpZHRoPTE5LjUsIG9uZWZpbGU9VCkKICBwcmludChzcHJpbnRmKCdmaWd1cmVzIHNhdmVkIGluIGZpbGUgJXMnLCBmaWxlX25hbWUpKQp9CgpnX2xpc3QgPSBsaXN0KCkKCgphbGxfbWV0aG9kcyA9IG5hbWVzKG1ldGhvZF9jb2xvcikKYWxsX2N0cyA9IGNvbG5hbWVzKGFsbF9yZXMkVHJ1dGgpCgpmb3IgKG9uZV9tZXRob2QgaW4gYWxsX21ldGhvZHMpIHsKICBwbG90X2RmID0gbWVyZ2UoYWxsX3JlcyRTMV9leHRfcmVmW1tvbmVfbWV0aG9kXV0sIGxvY19kZlssIGMoJ3gnLCAneScpXSwgYnk9J3Jvdy5uYW1lcycpCiAgZ19saXN0W1tsZW5ndGgoZ19saXN0KSsxXV0gPSBnZ3Bsb3QoKSArCiAgICBnZW9tX3NjYXR0ZXJwaWUoYWVzKHg9eCwgeT15KSwgZGF0YT1wbG90X2RmLCBjb2xzPWFsbF9jdHMpICsKICAgIHNjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcz1teV9jb2xvcikgKwogICAgdGhlbWVfY2xhc3NpYygpICsKICAgIGdndGl0bGUob25lX21ldGhvZCkgKwogICAgdGhlbWUoYXhpcy50aXRsZT1lbGVtZW50X2JsYW5rKCksIGF4aXMudGV4dD1lbGVtZW50X2JsYW5rKCksIGF4aXMudGlja3M9ZWxlbWVudF9ibGFuaygpLCBheGlzLmxpbmU9ZWxlbWVudF9ibGFuaygpLAogICAgICBsZWdlbmQudGl0bGU9ZWxlbWVudF9ibGFuaygpLCBsZWdlbmQudGV4dD1lbGVtZW50X3RleHQoc2l6ZT0xNSksCiAgICAgIHBsb3QudGl0bGU9ZWxlbWVudF90ZXh0KHNpemU9MTcsIGZhY2U9J2JvbGQnLCBoanVzdD0wLjEpKQp9CgpnZ3B1YnI6OmdnYXJyYW5nZShwbG90bGlzdCA9IGdfbGlzdCwgbmNvbCA9IDMsIG5yb3cgPSAzLCBhbGlnbiA9ICdodicsIGNvbW1vbi5sZWdlbmQgPSBULCBsZWdlbmQgPSAncmlnaHQnLCBmb250LmxhYmVsID0gbGlzdChzaXplPTE3KSkKYGBgCgoK